#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	priority_queue<int> a;
	priority_queue<int, vector<int>, greater<int>> b;
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;;
		if (b.empty() || x > b.top()) b.push(x);
		else a.push(x);

		int k = (i + 1) / 2;
		while (b.size() > k) a.push(b.top()), b.pop();
		while (b.size() < k) b.push(a.top()), a.pop();
		if (i & 1) cout << b.top() << endl;
	}
	return 0;
}